Formulas

Logical Equivalences

• Implication Equivalence:
• Biconditional Equivalence:
• Identity Law:
• Identity Law:
• Complement Law:
• Complement Law:
• Idempotent Law:
• Idempotent Law:
• Double Negation Law:
• Associative Law:
• Distributive Law:
• Distributive Law:
• De Morgan’s Law:
• De Morgan’s Law:
• Bi-implication Equivalence:
• Adjacency Law:
• Simplification Law:
• Contrapositive Equivalence:

Normal Forms (DNF, CNF, ANF)

• General Formula for DNF:
• General Formula for CNF:
• ANF Conjunction:
• ANF Negation:
• ANF Disjunction:
• ANF Implication:
• ANF Bi-implication:
• ANF Property (Idempotence):
• ANF Property (XOR with self):
• ANF Property (XOR Identity):

Predicate Logic

• De Morgan’s Law for Universal Quantifier:
• De Morgan’s Law for Existential Quantifier:
• Restricted Universal:
• Restricted Existential:

Set Theory

• Complement:
• Difference:
• De Morgan’s Law:
• De Morgan’s Law:
• Distributive Law:
• Cardinality of a Union (Two Sets):
• Cardinality of a Union (Three Sets):
• Cardinality of a Set Difference:
• Cardinality of a Cartesian Product:
• Intersection of Cartesian Products:
• Intersection of Power Sets:

Proofs and Number Theory

• Definition of an Odd Integer:
• Definition of an Even Integer:
• Sum of First Integers:
• Sum of First Squares:
• Sum of a Geometric Series:
• Fibonacci Recurrence Relation:
• Binet’s Formula:
• Sum of First Odd-Indexed Fibonacci Numbers:
• Bernoulli’s Inequality:

Combinatorics

• Ordered Arrangement with Repetition:
• Ordered Arrangement without Repetition (Permutation):
• Permutation of n distinct items:
• Unordered Arrangement without Repetition (Combination):
• Partitioning into Unordered Groups:
• Permutations with Repetition (Multinomial Coefficient):
• Coefficient of in :
• Coefficient of in :
• Unordered Arrangement with Repetition (Stars and Bars):
• Solutions to for :
• Complementary Counting:

Recurrence Relations

• Arithmetic Progression:
• Geometric Progression:
• Second-Order Recurrence General Solution (Distinct Roots ):
• Second-Order Recurrence General Solution (Repeated Root ):

Relations and Graph Theory

• Total Number of Binary Relations on Elements:
• Number of Reflexive Relations on Elements:
• Number of Irreflexive Relations on Elements:
• Number of Symmetric Relations on Elements:
• Number of Asymmetric Relations on Elements:
• Number of Anti-symmetric Relations on Elements:
• Number of Linear Orders on Elements:
• Asymmetric Relation Equivalence: Asymmetric Anti-symmetric Irreflexive
• Non-strict from Strict Order:
• Handshaking Lemma: (the sum of all degrees equals twice the number of edges)
• Number of Edges in Complete Graph :
• Degree of Vertices in : Each vertex has degree
• Degree of Vertices in : Each vertex has degree 2
• Number of Edges in :
• Number of Edges in Complete Bipartite Graph :
• Characteristic Property of Trees: A connected graph with vertices is a tree if and only if it has exactly edges
• Number of Edges in a Forest: A forest with vertices and components has exactly edges
• Number of Possible Simple Graphs of Order : (each potential edge can be present or absent)
• Number of Possible Bipartite Graphs with Sets and : (each potential edge between sets can be present or absent)

Eulerian and Hamiltonian Graphs

• Euler Cycle Condition: A non-trivial connected graph is Eulerian if and only if every vertex has even degree
• Euler Path Condition: A connected graph has an Euler path if and only if it has exactly zero or exactly two vertices with odd degree
• Complete Graph Eulerian: is Eulerian if and only if is odd
• Complete Bipartite Graph Eulerian: is Eulerian if and only if both and are even
• Complete Bipartite Graph Hamiltonian: is Hamiltonian if and only if
• Dirac’s Theorem (Sufficient Condition for Hamiltonian): Let be a simple graph with vertices. If for every vertex , then is Hamiltonian
• Ore’s Theorem (Sufficient Condition for Hamiltonian): Let be a simple graph with vertices. If for every pair of non-adjacent vertices and , then is Hamiltonian

Planar Graphs and Colourings

• Euler’s Formula (Planar Graphs): , where = vertices, = edges, = faces (including exterior face)
• Edge Bound for Planar Graphs: If is a connected planar graph with , then
• Edge Bound for Bipartite Planar Graphs: If is a connected bipartite planar graph with , then
• Face-Edge Inequality (General): (each face has at least 3 edges, each edge borders at most 2 faces)
• Face-Edge Inequality (Bipartite): (bipartite graphs have no triangles, so each face has at least 4 edges)
• Chromatic Number of Complete Graph:
• Chromatic Number of Null Graph: (graph with no edges)
• Chromatic Number of Bipartite Graph: for any non-trivial bipartite graph
• Chromatic Number of Odd Cycle:
• Chromatic Number of Even Cycle:
• Four Colour Theorem: for any planar graph
• Kuratowski’s Theorem: A graph is planar if and only if it does not contain a subgraph that is a subdivision of or